package leetcode.day_2021_03_8_2021_03_14;

import java.util.*;

/**
 * 56. 合并区间
 * https://leetcode-cn.com/problems/merge-intervals/
 * [[1,3],[2,6],[8,10],[15,18]]
 */
public class LeetCode0056 {

    public static void main(String[] args) {
        int[][] arr = {{1,3}, {2,6}, {8,10}, {15,18}};
        int[][] res = merge2(arr);
        for (int i=0; i< res.length; i++) {
            System.out.println(Arrays.toString(res[i]));
        }
    }

    public static int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if (n == 1) return intervals;
        List<int[]> list = new ArrayList();
        for (int i=0; i<intervals.length; i++) {
            list.add(intervals[i-1]);
            if (intervals[i][1] >= intervals[i+1][0]) {
                list.remove(list.size()-1);
                list.add(new int[]{intervals[i][0], intervals[i+1][1]});
            } else {
                list.add(intervals[i]);
            }
        }
        int[][] arr = new int[list.size()][];
        for (int i=0; i<list.size(); i++) {
            arr[i] = list.get(i);
        }
        Arrays.sort(arr, Comparator.comparingInt(num -> num[0]));
        return arr;
    }

    public static int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(num1 -> num1[0]));
        int[][] res = new int[intervals.length][2];
        int index = -1;
        for (int[] interval : intervals) {
            if (index==-1 || interval[0] > res[index][1]) {
                res[++index] = interval;
            } else {
                res[index][1] = Math.max(interval[1], res[index][1]);
            }
        }
        return Arrays.copyOf(res, index+1);
    }
}
